\section{An $O((n+k)\log n)$ round algorithm}
In this section, we present an $O(n \log n)$ round centralized
algorithm for the $k$-gossip problem on any dynamic network in the
offline model for any $k \le n$.  Our bound is tight to within an
$O(\log n)$ factor since the dissemination of any $k$ tokens to even a
single node of the network will take $\Omega(n + k)$ rounds in the
worst case.

\begin{lemma}
\label{lem:tree_partition}
For any $r \le n/2$, the edges of any tree $T$ over $n$ vertices can
be partitioned into $r$ sets $T_1$, $T_2$, \ldots, $T_r$, where each
$T_i$ is connected and has $O(n/r)$ edges.
\end{lemma}

\begin{lemma}
Let $S$ denote a set of $r$ sources and $T$ a set of $r$ sinks, each
set drawn independently and uniformly at random from $V$.  In the
time-expanded graph $\expandedG$ over $\Theta(n + k)$ rounds, the
maximum flow from the super-source to the super-sink is at least $rk$
with high probability.
\end{lemma}
\begin{proof}
We show that with high probability, the capacity of every cut is at
least $rk$.  Consider any cut $C = (\S, \T)$ of $\expandedG$.  If any
of the sources in $S$ is separated from the super-source, then the
capacity of the cut is at least $rk$ since the capacity of the edge
connecting the super-source to any source is $rk$.  So in the
remainder, we assume that all vertices in $S$ are on the same side of
the cut as the super-source.  Let $T'$ denote the set of sources that
are separated from the super-source in $C$; let $r' = |T'|$.  All of
the edges from $T - T'$ to the super-sink cross $C$ and have a total
capacity of $(r - r')k$.  It thus remains to show that the total
capacity of the edges crossing the cut in the intermediate levels $1$
through $t$ is at least $r'k$.

Let $V_i$ denote the set of vertices in level $i$ that are in $\S$.
Since every parallel edge has infinite capacity, we have $V_{i+1}
\superseteq V_i$.  Since each $V_i$ is of size at most $n$, there are
at least $t - n$ levels such that $V_{i+1} = V_i$.  For any such level
$i$, $C$ includes all edges that separate $S$ from $T'$ in the graph
$G_i$.  We show that the capacity of this cut in $G_i$ is
$\Omega(r')$.  For $t$ exceeding $\Omega(k)$, it then follows that the
total capacity of the edges crossing the cut in the intermediate
levels $1$ through $t$ is at least $r'k$.

Consider graph $G_i$ with given vertex sets $S$, $T$, and $T'$.
Recall that $S$ and $T$ are drawn uniformly at random from the
collection of all $r$-vertex sets, and $T'$ is an arbitrary subset of
$T$ of size $r'$.  By Lemma~\ref{lem:tree} applied to a spanning tree
of $G$, there exist edge-disjoint subgraphs $G_1$, $G_2$, \ldots,
$G_r$ each having $O(n/r)$ edges from the spanning tree.  Since $S$
and $T$ are drawn at random, it follows that each of these $r$
subgraphs has $O(\log n/\log\log n)$ nodes in $T$ whp.

\end{proof}
